package com.bigshen.algorithm.fSort.solution02QuickMerge;

public class Solution {

    // 冒泡、插入、选择排序
    // 快速排序
    // 归并排序
    public int[] sortArray(int[] nums) {

        if (null == nums || nums.length < 2) {
            return nums;
        }

        // 4,5,2,3,1
        // 快速排序
        quickSort(nums, 0, nums.length-1);

        // 归并排序
        //int[] tmp = new int[nums.length];
        //mergeSort(nums, 0, nums.length-1, tmp);
        return nums;
    }

    // 归并排序 借助辅助数组进行排序，分治法
    private void mergeSort(int[] array, int start, int end, int[] tmp) {

        if (start >= end) {
            return;
        }

        int mid = start + (end-start)/2;
        mergeSort(array, start, mid, tmp);
        mergeSort(array, mid+1, end, tmp);
        merge(array, start, mid, end, tmp);
    }

    private void merge(int[] array, int start, int mid, int end, int[] tmp) {

        int left = start;
        int right = mid+1;
        int index = start;
        while(left <= mid && right <= end) {
            if (array[left] < array[right]) {
                // 小的先入队
                tmp[index++] = array[left++];
            } else {
                tmp[index++] = array[right++];
            }
        }
        while(left <= mid) {
            tmp[index++] = array[left++];
        }
        while(right <= end) {
            tmp[index++] = array[right++];
        }
        for (int i = start; i <= end; i++) {
            array[i] = tmp[i];
        }

    }



    // 快速排序， 节点互换位置
    public void quickSort(int[] array, int start, int end) {

        if (start >= end) {
            return;
        }

        int tmp = array[start];
        int left = start;
        int mid = start + (end-start)/2;
        int right = end;
        while (left < right) {
            while(left < right && array[right] >= tmp) {
                right--; // 从右侧向左找比tmp小的数
            }
            if (left < right && array[right] < tmp) {
                // 右侧小的值移至左侧，右侧有一个坑位
                array[left] = array[right];
                left++;
            }

            while(left < right && array[left] <= tmp) {
                left++; // 从左侧向右找比tmp大的数
            }
            if (left < right && array[left] > tmp) {
                // 左侧大的值移至右侧，左侧有一个坑位
                array[right] = array[left];
                right--;
            }
        }

        array[left] = tmp;

        quickSort(array, start, left-1);
        quickSort(array, left+1, end);

    }

    public static void main(String[] args) {

        int[] array = {5,2,7,6,3,9,8};

        new Solution().sortArray(array);
        
        for (int element : array) {
            System.out.println(element);
        }

    }

}
